home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 8238 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.9 KB

  1. Path: ix.netcom.com!news
  2. From: Norman Bullen <nbullen@ix.netcom.com>
  3. Newsgroups: comp.lang.c
  4. Subject: Re: need psudeo code for binary search
  5. Date: Sat, 02 Mar 1996 08:30:30 -0800
  6. Organization: Black Cat Associates
  7. Message-ID: <313877A6.4047@ix.netcom.com>
  8. References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix> <4h77mu$qtb@news1.cle.ab.com>
  9. NNTP-Posting-Host: ple-ca9-22.ix.netcom.com
  10. Mime-Version: 1.0
  11. Content-Type: text/plain; charset=us-ascii
  12. Content-Transfer-Encoding: 7bit
  13. X-NETCOM-Date: Sat Mar 02 10:42:12 AM CST 1996
  14. X-Mailer: Mozilla 2.0 (Win16; I)
  15.  
  16. Donald-Anthony C. Phillips wrote:
  17. > The binary search algorithm works as follows:
  18. > 1) Remember the structure must already be sorted.
  19. > 2) It works better as a recursive function 
  20. It actually works better when written as a loop because it will use much 
  21. less stack space.
  22.  
  23. int BinarySearch(char *pstrTarget, char *pstrTable[], int tableSize)
  24. {  int comp, hi, lo, look;
  25.  
  26.    hi = tableSize-1; lo = 0;
  27.    while (hi>=lo) {
  28.       look = (hi+lo)/2;
  29.       comp = strcmp(pstrTarget, pstrTable[look]);
  30.       if (comp==0) return look; /* Found it! */
  31.       if (comp>0)
  32.          lo = look+1;
  33.       else
  34.          hi = look-1;
  35.                   }
  36.    return 0; /* Didn't find it. */
  37. }
  38.  
  39. I've assumed that you meant to search an array of strings, not an array 
  40. of chars.
  41.  
  42. The idea of a binary search is to split the search area into two (more or 
  43. less) equal parts and look at the item that falls in the middle. If its 
  44. the one you're looking for you are done. Otherwise, if the item you are 
  45. looking for is greater that the one you just looked at you know that it 
  46. will be in the upper of the two parts. If less, in the lower of the two 
  47. parts. If its not there at all, eventually the range of items collapses 
  48. and you drop out of the loop.
  49.  
  50. (You may have to play with that piece of code a little; I think its right 
  51. but I did not attempt any sort of testing.)
  52.